package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.PriorityQueue;

public class Day26 {

    /***
     * 已知一个几乎有序的数组，几乎有序指，如果数组排好序的话，
     * 每一个元素移动的距离不超过k，并且k远小于数组大小，请给出最合适的排序算法
     * @param arr
     */
    public static void sortedArrDistanceLessThanK(int[] arr, int k) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int heapSizeMax = Math.min(arr.length, k);
        PriorityQueue<Integer> heap = new PriorityQueue<>(heapSizeMax);
        int index = 0;
        for (; index <= heapSizeMax && index < arr.length; index++) {
            heap.add(arr[index]);
        }
        int currentSortIndex = 0;
        for (; index < arr.length; currentSortIndex++, index++) {
            heap.add(arr[index]);
            arr[currentSortIndex] = heap.poll();
        }
        while (!heap.isEmpty()) {
            arr[currentSortIndex++] = heap.poll();
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 12, 12, 5, 3, 10, 9};
        sortedArrDistanceLessThanK(arr, arr.length);
        ArrayUtils.print(arr);
    }
}
